1. Field of the Invention
The present invention relates to data storage devices, and in particular relates to improved techniques for using and managing non-volatile memory storage devices to enhance lifetime characteristics of such devices.
2. Background of the Invention
Memory devices are a key component in today's computer systems, allowing high-speed access to retrieve and store data. A certain type of memory device known as non-volatile memory maintains the correct data value stored in the device even when power is removed from the device. Because non-volatile memory devices are more expensive than volatile memory devices (which lose data when removed from a power source), their use in a computer system is typically limited to situations where a need exists to maintain data even when power is removed or lost. For example, configuration settings for a computer are typically stored in non-volatile memory so that the system properly boots-up in a proper state when powered-up. These configuration settings may include the number and type of peripheral devices that are attached to a computer, the current date/time, power management settings, etc. Another use of non-volatile memory in a computer system is to store the initial boot-up code that gets executed when the computer is first turned on. This initial code, sometimes called BIOS when discussing personal computers, provides the computer with enough programming capability to allow it to initialize a computer and read an operating system from a storage device such as a hard disk.
Technological advances and volume production have driven the cost of such non-volatile storage devices down so that other types of devices, such as consumer devices, can now cost-effectively include and utilize non-volatile memory for their own advantage. Cellular telephones can be programmed to store phone lists, for example. Digital cameras store snapped photographs in non-volatile memory devices. Music devices such as MP3 players also use non-volatile memory to store music. Because of the reduction in price of these non-volatile memory devices due to volume production, it is now possible to envision use of these devices in mass data storage systems, in lieu of or in addition to disk arrays or tape library systems.
One type of non-volatile memory device is known as an electrically erasable and programmable read only memory (EEPROM), which is a particular type of integrated circuit (IC) device. Another integrated circuit non-volatile memory device is a non-volatile random access memory (NVRAM), which is a combination of static RAM (SRAM) and EEPROM. These devices are made up of an array of cells which store data bits that have been programmed into the device. The EEPROM device is programming by providing particular voltages to certain portions of transistors (such as gate, drain and source terminals) that are used in each cell. The device is read by providing particular, but different, voltages to certain portions of transistors. It is also possible to erase the content of a cell by applying a particular voltage to an erase gate. Similarly, a NVRAM is written to by writing data into the device using conventional SRAM writing techniques, and the SRAM data is copied to the EEPROM when power is removed in order to maintain the data in the EEPROM when no power exists.
A large number of cells are typically configured to form a non-volatile memory device. They may be fashioned in a two-dimensional array, with each cell being individually addressable for reading or writing. However, to reduce design complexity (and cost), groups of cells share certain common control lines for erasing the cell. The cells that share a common erase control are typically called a block of cells, or a block. Block sizes can be any size as dictated by a given design, and may be 128 bits, 256 bits, 1024 bits, etc. All the bits in a block are erased at the same time during an erase operation using the common erase control line, and this is sometimes referred to as erasing ‘in a flash’. Because of this, certain non-volatile memory such as EEPROM that is erased and reprogrammed at the block level (as opposed to a byte level) has become known as flash memory.
In what follows the term “physical block” refers to a block in the sense just described; that is, a physical block is the smallest group of cells of flash memory that can be erased or rewritten at one time. A “logical block,” on the other hand, refers to the data that is stored in a physical block. To simplify the explanations, an empty physical block is regarded as a physical block that contains a logical block that has never been modified.
Certain non-volatile memory devices such as EEPROM age over time, and thus have a limit on the number of times they can be re-programmed. This ‘aging’ is not necessarily caused by how old the device is, but rather by how many times the device has been written to. Each physical block has a finite lifetime in terms of the number of erase/write cycles that it can undergo. For present flash memory technology, this endurance limit is approximately 100,000 to 1,000,000 cycles. Because of this limitation, the useful life of a flash memory terminates as soon as one physical block has reached its endurance limit (unless spare blocks have been held in reserve). For many consumer applications, this relatively large number is generally not an issue. However, when these devices are used in applications having a large amount of input and output operations—such as when used in conjunction with or in lieu of a disk or tape subsystem—it does become an issue.
In those applications where the endurance limit does pose a significant restriction on the lifetime of the device, the lifetime of the device can be extended by taking steps to ensure that wear is distributed more evenly over all the physical blocks. To cite an extreme example, if only one logical block is modified frequently and no steps are taken to redistribute the wear, the useful lifetime of the device terminates as soon as the physical block containing the mentioned logical block reaches the endurance limit. However, if the active logical block is moved from one physical block to another at suitable intervals, the lifetime of the memory can be multiplied by the number of physical blocks in the flash memory. This illustrates the wear-leveling method for memory extension. The problem is to devise a wear-leveling algorithm that can be relied upon to distribute wear more evenly, with acceptable overheads, under conditions that can be expected to arise in practice.
One approach to wear leveling for flash EEPROM systems is described in U.S. Pat. No. 6,230,233. The EEPROM array is divided into two or more interchangeable banks of physical blocks. A memory controller provides for interchanging the banks when it is detected that they are receiving significantly uneven use. However, this technique is deficient in several respects (the following critique refers to individual physical blocks rather than banks merely for simplicity):
1. The choice of logical blocks to be moved in a wear-leveling operation is based on the cumulative wear of a given physical block, which depends on all the logical blocks that have resided in that physical block since the device began operation; the activity level of the logical block currently stored in the physical block is thereby obscured, leading to suboptimal decisions. For example, it would be desirable to populate the most worn physical block with the least active logical block, but the logical block currently residing in the least worn physical block (i.e., the physical block with the smallest cumulative wear) is not necessarily the least active logical block.2. Wear-leveling operations can be counterproductive if they are performed too frequently: a logical block that is frequently modified and has been moved from a physical block with high wear to a physical block with low wear may be moved back to the physical block with high wear.
In view of these deficiencies in the technique taught in U.S. Pat. No. 6,230,233, it would be desirable to provide a wear-leveling technique for non-volatile memory devices that could be relied upon to yield satisfactory results with greater consistency.